//
// Created by LiuYou on 2021/5/24.
//

#include <unordered_map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <climits>

#define DEBUG

static std::pair<std::string, int>
findLowestCostNode(std::__umap_hashtable<std::string, int>& costs,
                   std::vector<std::pair<std::string, int>>& processed);

static void DijkstraAlgorithm(std::__umap_hashtable<std::string, std::__umap_hashtable<std::string, int>>& graph,
                              std::__umap_hashtable<std::string, int>& costs,
                              std::__umap_hashtable<std::string, std::string>& parent,
                              std::vector<std::pair<std::string, int>>& processed);

/**
 * @brief 04 版本完成了任务！！！！！！！！！
 * @return
 */
int main() {
    // 使用散列表存储邻居和前往邻居的开销
    std::__umap_hashtable<std::string, std::__umap_hashtable<std::string, int>> graph;
    graph["start"] = {};
    graph["start"]["a"] = 6;
    graph["start"]["b"] = 2;

    std::cout << graph["start"]["a"] << std::endl;
    std::cout << graph["start"]["b"] << std::endl;

    graph["a"] = {};
    graph["a"]["final"] = 1;
    graph["b"] = {};
    graph["b"]["a"] = 3;
    graph["b"]["final"] = 5;
    graph["final"] = {};

    // 使用散列表存储每个结点的开销
    std::__umap_hashtable<std::string, int> costs;
    costs["a"] = 6;
    costs["b"] = 2;
    // py中可以表示无穷大, 但是C++中设置一个标志数即可。这里我设置成了 -1 。
    // 不行, 这里不能设置为 -1 , 因为后续操作算法要对cost哈希表中的元素比较大小！！！！
    costs["final"] = INT_MAX;

    // 还需要一个散列表, 这个散列表存储父结点
    std::__umap_hashtable<std::string, std::string> parent;
    parent["a"] = "start";
    parent["b"] = "start";
    parent["final"] = "";
    std::cout << "parent.size(): " << parent.size() << std::endl;
    for (const auto& item : parent) {
        std::cout << item.first << " -> " << item.second << " -> ";
    }
    std::cout << std::endl;


    // 还需要一个数组来记录处理过的结点。
    std::vector<std::pair<std::string, int>> processed;

    // Dijkstra算法。
    DijkstraAlgorithm(graph, costs, parent, processed);

//    for (const auto& item : parent) {
//        std::cout << item.second << std::endl;
//    }
    std::cout << "parent.size(): " << parent.size() << std::endl;
    for (const auto& item : parent) {
        std::cout << item.first << " -> " << item.second << " -> ";
    }
    std::cout << std::endl;


    std::exit(0);
}

static void
DijkstraAlgorithm(std::__umap_hashtable<std::string, std::__umap_hashtable<std::string, int>>& graph,
                  std::__umap_hashtable<std::string, int>& costs,
                  std::__umap_hashtable<std::string, std::string>& parent,
                  std::vector<std::pair<std::string, int>>& processed) {
//     下面实现狄克斯特拉算法
//    const std::pair<std::string, int>& lowestCostNode = findLowestCostNode(costs);
    std::pair<std::string, int> node = findLowestCostNode(costs, processed);

    while (node != std::pair<std::string, int>()) {
        // 获取该结点的开销
        std::pair<std::string, int> cost = *costs.find(node.first);
        // 获取该结点的邻居
        std::__umap_hashtable<std::string, int> neighbors = graph[node.first];

#ifdef DEBUG
        // 加一些调试信息
        {
            std::cout << std::endl << "========================================" << std::endl;
            for (const auto& item : neighbors) {
                std::cout << item.first << " " << item.second << std::endl;
            }
            std::cout << "========================================" << std::endl;
        }
#endif

        for (const auto& item : neighbors) {
            std::pair<std::string, int> newCost(cost.first, cost.second + item.second);

            // TODO 注意:
            if (costs[item.first] > newCost.second) {
                costs[item.first] = newCost.second;
                parent[item.first] = node.first;

            }


#ifdef DEBUG
            // 加入调试信息
            {
                std::cout << std::endl << "========================================" << std::endl;
                for (const auto& item : costs) {
                    std::cout << item.first << " " << item.second << std::endl;
                }
                std::cout << "========================================" << std::endl;
                std::cout << std::endl << "========================================" << std::endl;
                for (const auto& item : parent) {
                    std::cout << item.first << " " << item.second << std::endl;
                }
                std::cout << "========================================" << std::endl;
            }
#endif

        }

        // TODO 注意: 原因终于终于终于找出来了, 原因是: 这里虽然加入到了 processed数组中, 但是在进行
        //  下面的 findLowestCostNode()函数时, 依然会返回一样的结果。使上面的for循环一直重复！！！！
        processed.push_back(node);
//        const std::pair<std::string, int>& node = findLowestCostNode(costs);
        node = findLowestCostNode(costs, processed);
    }
}

/*
 * TODO 注意: 这个函数真的真的真的真的非常重要, 我要被这个函数折磨疯了！！！！！！！！！！！！！！！
 *   现在这个03版本基本上都好了, 就是这个最后的有一点问题。
 *
 * TODO 注意: 04终于运行成功了！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
 *   ！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
 *   ！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
 *   卧槽！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
 *   卧槽！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
 *   卧槽！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
 *   卧槽！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
 *   真的无语, 终于成功了！！！！！！现在这个 04 版本已经完成任务了, 05版本进行最后的一些改进。
 *   见 05 版本。
 */
static std::pair<std::string, int>
findLowestCostNode(std::__umap_hashtable<std::string, int>& costs,
                   std::vector<std::pair<std::string, int>>& processed) {
    int lowestCost = INT_MAX;
    std::pair<std::string, int> node{};

#ifdef DEBUG
    // 加一些调试信息
    {
        std::cout << std::endl << "========================================" << std::endl;
        for (const auto& item : costs) {
            std::cout << item.first << " " << item.second << std::endl;
        }
        std::cout << "========================================" << std::endl;
    }
#endif

    bool flg;
    for (const auto& item : costs) {
        int cost = item.second;
        if (cost < lowestCost /* && item不在processed内 */) {
            if (processed.empty()) {
                lowestCost = cost;
                node = item;
            } else {
                // TODO 注意: 这里真的头疼。vector。

                // flag
                for (const auto& elem : processed) {
                    if (item.first != elem.first) {
                        flg = true;
                    } else {
                        flg = false;
                        break;
                    }

//                    if (item.first != elem.first) {
//                        lowestCost = cost;
//                        node = item;
//                    } else if (item.first == elem.first) {
//                        break;
//                    }


                }

                if (flg) {
                    lowestCost = cost;
                    node = item;
                }


            }
        }
    }



/*    for (const auto& item : costs) {
        int cost = item.second;
        if (cost < lowestCost *//* && item不在processed内 *//*) {
            if (processed.empty()) {
                lowestCost = cost;
                node = item;
            } else {
                // TODO 注意: 这里真的头疼。vector。
                for (const auto& elem : processed) {
                    if (item.first != elem.first) {
                        lowestCost = cost;
                        node = item;
                    } else if (item.first == elem.first) {
                        break;
                    }
                }
            }
        }
    }*/


    /*  {
          std::pair<std::string, int> node = *costs.cbegin();
  //    std::pair<std::string, int> node{};
          bool flag = false;


          for (const auto& item : costs) {

              // 条件限制。
              if (processed.empty()) {
                  // true为不在processed中。
                  flag = true;
              } else {
                  for (const auto& elem : processed) {
                      if (elem.first == item.first) {
                          flag = false;
                          break;
                      }
                  }
              }

              if (item.second < node.second && flag) {
                  node = item;
              }
          }
      }*/

    return node;
}





//static std::pair<std::string, int>
//findLowestCostNode(std::__umap_hashtable<std::string, int>& costs,
//                   std::vector<std::pair<std::string, int>>& processed) {
//    std::pair<std::string, int> node = *costs.cbegin();
////    std::pair<std::string, int> node{};
//    bool flag = false;
//
//
//    for (const auto& item : costs) {
//
//        // 条件限制。
//        if (processed.empty()) {
//            // true为不在processed中。
//            flag = true;
//        } else {
//            for (const auto& elem : processed) {
//                if (elem.first == item.first) {
//                    flag = false;
//                    break;
//                }
//            }
//        }
//
//        if (item.second < node.second && flag) {
//            node = item;
//        }
//    }
//
//    return node;
//}




//static std::pair<std::string, int>
//findLowestCostNode(std::__umap_hashtable<std::string, int>& costs,
//                   std::vector<std::pair<std::string, int>>& processed) {
//    std::pair<std::string, int> node = *costs.cbegin();
//    for (const auto& item : costs) {
//        if (processed.empty()) {
//            if (item.second < node.second) {
//                node = item;
//            }
//        } else {
//            for (const auto& elem : processed) {
//                if (item.first == elem.first) {
//                    break;
//                } else {
//                    if (item.second < node.second) {
//                        node = item;
//                    }
//                }
//            }
//        }
//    }
//    return node;
//}

//static std::pair<std::string, int>
//findLowestCostNode(std::__umap_hashtable<std::string, int>& costs,
//                   std::vector<std::pair<std::string, int>>& processed) {
//    std::pair<std::string, int> node = *costs.cbegin();
//    for (const auto& item : costs) {
//        if (processed.empty()) {
//            if (item.second < node.second) {
//                node = item;
//            }
//        } else {
//            for (const auto& elem : processed) {
//                if (item.first == elem.first) {
//                    break;
//                } else {
//                    if (item.second < node.second) {
//                        node = item;
//                    }
//                }
//            }
//        }
//
//    }
//    return node;
//}
